Internet Surfer 2.0

home *** CD-ROM | disk | FTP | other *** search

/ Internet Surfer 2.0 / Internet Surfer 2.0 (Wayzata Technology) (1996).iso / pc / text / mac / faqs.464 < prev next >

Wrap

Text File | 1996-02-12 | 28.2 KB | 1,044 lines

Frequently Asked Questions (FAQS);faqs.464 ==> games/connect.four.p <== Is there a winning strategy for Connect Four? ==> games/connect.four.s <== An AI program has solved Connect Four for the standard 7 x 6 board. The conclusion: White wins, was confirmed by the brute force check made by James D. Allen, which has been published in rec.games.programmer. The program called VICTOR consists of a pure knowledge-based evaluation function which can give three values to a position: 1 won by white, 0 still unclear. -1 at least a draw for Black, This evaluation function is based on 9 strategic rules concerning the game, which all nine have been (mathematically) proven to be correct. This means that a claim made about the game-theoretical value of a position by VICTOR, is correct, although no search tree is built. If the result 1 or -1 is given, the program outputs a set of rules applied, indicating the way the result can be achieved. This way one evaluation can be used to play the game to the end without any extra calculation (unless the position was still unclear, of course). Using the evaluation function alone, it has been shown that Black can at least draw the game on any 6 x (2n) board. VICTOR found an easy strategy for these boardsizes, which can be taught to anyone within 5 minutes. Nevertheless, this strategy had not been encountered before by any humans, as far as I know. For 7 x (2n) boards a similar strategy was found, in case White does not start the game in the middle column. In these cases Black can therefore at least draw the game. Furthermore, VICTOR needed only to check a few dozen positions to show that Black can at least draw the game on the 7 x 4 board. Evaluation of a position on a 7 x 4 or 7 x 6 board costs between 0.01 and 10 CPU seconds on a Sun4. For the 7 x 6 board too many positions were unclear. For that reason a combination of Conspiracy-Number Search and Depth First Search was used to determine the game-theoretical value. This took several hundreds of hours on a Sun4. The main reason for the large amount of search needed, was the fact that in many variations, the win for White was very difficult to achieve. This caused many positions to be unclear for the evaluation function. Using the results of the search, a database will be constructed of roughly 500.000 positions with their game-theoretical value. Using this datebase, VICTOR can play against humans or other programs, winning all the time (playing White). The average move takes less than a second of calculation (search in the database or evaluation of the position by the evaluation function). Some variations are given below (columns and rows are numbered as is customary in chess): 1. d1, .. The only winning move. After 1. .., a1 wins 2. e1. Other second moves for White has not been checked yet. After 1. .., b1 wins 2. f1. Other second moves for White has not been checked yet. After 1. .., c1 wins 2. f1. Only 2 g1 has not been checked yet. All other second moves for White give Black at least a draw. After 1. .., d2 wins 2. d3. All other second moves for White give black at least a draw. A nice example of the difficulty White has to win: 1. d1, d2 2. d3, d4 3. d5, b1 4. b2! The first three moves for White are forced, while alternatives at the fourth moves of White are not checked yet. A variation which took much time to check and eventually turned out to be at least a draw for Black, was: 1. d1, c1 2. c2?, .. f1 wins, while c2 does not. 2. .., c3 Only move which gives Black the draw. 3. c4, .. White's best chance. 3. .., g1!! Only 3 .., d2 has not been checked completely, while all other third moves for Black have been shown to lose. The project has been described in my 'doctoraalscriptie' (Master thesis) which has been supervised by Prof.Dr H.J. van den Herik of the Rijksuniversiteit Limburg (The Netherlands). I will give more details if requested. Victor Allis. Vrije Universiteit van Amsterdam. The Netherlands. victor@cs.vu.nl ==> games/craps.p <== What are the odds in craps? ==> games/craps.s <== The game of craps: There is a person who rolls the two dice, and then there is the house. 1) On the first roll, if a 7 or 11 comes up, the roller wins. If a 2, 3, or 12 comes up the house wins. Anything else is a POINT, and more rolling is necessary, as per rule 2. 2) If a POINT appears on the first roll, keep rolling the dice. At each roll, if the POINT appears again, the roller wins. At each roll, if a 7 comes up, the house wins. Keep rolling until the POINT or a 7 comes up. Then there are the players, and they are allowed to place their bets with either the roller or with the house. ----- My computations: On the first roll, P.roller.trial(1) = 2/9, and P.house.trial(1) = 1/9. Let P(x) stand for the probability of a 4,5,6,8,9,10 appearing. Then on the second and onwards rolls, the probability is: Roller: --- (i - 2) P.roller.trial(i) = \ P(x) * ((5/6 - P(x)) * P(x) (i > 1) / --- x = 4,5,6,8,9,10 House: --- (i - 2) P.house.trial(i) = \ P(x) * ((5/6 - P(x)) * 1/6 (i > 1) / --- x = 4,5,6,8,9,10 Reasoning (roller): For the roller to win on the ith trial, a POINT should have appeared on the first trial (the first P(x) term), and the same POINT should appear on the ith trial (the last P(x) term). All the in between trials should come up with a number other than 7 or the POINT (hence the (5/6 - P(x)) term). Similar reasoning holds for the house. The numbers are: P.roller.trial(i) (i > 1) = (i-1) (i-1) (i-1) 1/72 * (27/36) + 2/81 * (26/36) + 25/648 * (25/36) P.house.trial(i) (i > 1) = (i-1) (i-1) (i-1) 2/72 * (27/36) + 3/81 * (26/36) + 30/648 * (25/36) ------------------------------------------------- The total probability comes to: P.roller = 2/9 + (1/18 + 4/45 + 25/198) = 0.4929292929292929.. P.house = 1/9 + (1/9 + 2/15 + 15/99) = 0.5070707070707070.. which is not even. =========================================================================== == Avinash Chopde (with standard disclaimer) abc@unhcs.unh.edu, abc@unh.unh.edu {.....}!uunet!unh!abc ==> games/crosswords/cryptic/clues.p <== What are some clues (indicators) used in cryptics? Xref: bloom-picayune.mit.edu rec.puzzles:18144 news.answers:3075 Newsgroups: rec.puzzles,news.answers Path: bloom-picayune.mit.edu!enterpoop.mit.edu!snorkelwacker.mit.edu!usc!wupost!darwin.sura.net!haven.umd.edu!uunet!questrel!chris From: uunet!questrel!chris (Chris Cole) Subject: rec.puzzles FAQ, part 8 of 15 Message-ID: <puzzles-faq-8_717034101@questrel.com> Followup-To: rec.puzzles Summary: This posting contains a list of Frequently Asked Questions (and their answers). It should be read by anyone who wishes to post to the rec.puzzles newsgroup. Sender: chris@questrel.com (Chris Cole) Reply-To: uunet!questrel!faql-comment Organization: Questrel, Inc. References: <puzzles-faq-1_717034101@questrel.com> Date: Mon, 21 Sep 1992 00:09:26 GMT Approved: news-answers-request@MIT.Edu Expires: Sat, 3 Apr 1993 00:08:21 GMT Lines: 2382 Archive-name: puzzles-faq/part08 Last-modified: 1992/09/20 Version: 3 ==> games/crosswords/cryptic/clues.s <== The following list is derived from indicators used in a variety of crosswords: the letters in the left column are the letters being indicated; the right hand column is how these letters might be indicated in a clue. Caveat emptor: many of the entries in this list would be considered unsound in some puzzles (some of these unsound indicators are marked with a +). Entries marked * are used mostly in advanced cryptics. I would welcome corrections and additions to the list. ---------------------------------------------------------------------- a Austria a I a academician a accepted a ace a acre a active a adult a advanced a afternoon a aleph a alpha a amateur a ampere a an/ane a angstrom a answer a ante a are (metric) a articles - English a associate a atomic a ay a aye a before a blood group a bomb a effect a examination a fifty a film a first character a first class a first letter a five hundred a five thousand a good a high class a it a key + a level a midday a note + a one * a paper a road a strings (violin) a un a unit a violin string a vitamin a year aa motoring organisation ab able seaman ab hand ab rating ab sailor/salt/seaman ab tar abbe priest (Fr.) abe Lincoln abel first victim abel murder victim abel second child abel third man able can able expert abo native ac account ac accountant ac aircraftsman ac alternating current ac before Christ ac bill ac current aca accountant acas peacemakers acc account acc bill ace card ace champion ace expert ace one ace pilot ace service ace winner act decree act performance actor tree ad Christian era ad advertisement ad after date ad before the day ad contemporary ad in the modern age ad in the year of our Lord ad modern times ad notice ad now ad nowadays ad our time/era ad period ad present day ad promotion ad puff ad this era ad today adam first character adam first person adam number one add sum add tot aden port admin management admin running ado business ado difficulty ado fuss ado row ado trouble ae aged ae poet aet aged ag silver aga Muslim leader age (long) time age mature age period agent spy agm annual meeting agm meeting agm yearly meeting ai capital ai first class ai good ai high class ai main road ai sloth ail trouble ain own (Scot.) air appearance air display air song aire river ait island al Alabama al Alan al Albania al Albert al Capone al aluminium al gangster al one pound ala Alabama ala after the style of ala in the style of ala to the (Fr.) ala wings alas Alaska alb one pound ale beer aleph Hebrew letter all completely all everybody all everything alp mountain alp peak alph river alpha Greek letter alpha beginning alpha first character alpha first letter am America am American am I am am admitting am boasting am half day am hymns am in the morning am morning am self-confessed amen final word amen last word amer American ammo missiles amos bookmaker amp one member an I an articles - English an before an if (old word) an one * an un ana tales ane I ane one ane one ankh life symbol anne princess anon now ans answer ans brief reply ans collection ans short answer ant if it (old word) ant six-footer ant social worker ant soldier ant worker ape copy ape primate aq water ar arrive/arrival ar year of reign ara academician ara artist ara painter arab horse arc curve argo old ship aria song arm gun arm limb arm member arr arrive/arrival art contrivance art craft art cunning art painting art skill as Anglo-Saxon as ayes as ays as like as one's as specifically as when ash remains ash tree asia continent aside one fifteen asis existing state asp snake ass donkey asti wine ate goddess ate mischief athena goddess ation at one on atoll bikini au gold au to the (Fr.) aus Australia aux to the (Fr.) av bible av lived so long ave average ave greeting ave hail ave road ave way aver average avon county ay I ay agreement ay always ay ever ay yes aye I aye I say aye agreement aye always aye ever aye yes az Azed az scope, plenty of b Bach b Beethoven b Belgium b Brahms b Britain b British b a follower b bachelor b baron b bedbug b bee b bel b beta b beth b bishop b black b blood group b bloody b book * b born b boron b bowled b boy b breadth b inferior b key + b magnetic flux b note + b paper b second b second class b second letter b three hundred b three thousand b vitamin ba Bachelor of Arts ba airline ba bachelor ba barium ba degree ba graduate ba scholar bac airline bacon philosopher ban curse ban outlaw ban prohibition bar Inn bar lawyers bar prevent bar save barb horse bat fly-by-night bb bees bb books bb very black bc ancient times bc before Christ bc period bd beady bd bound bd cleric bd theologian be exist be live bea airline bear speculator bed in bed bee buzzer bee group of workers bee six-footer bee social worker bee worker bef Gort's men bess queen beta Greek letter beth Hebrew letter bi double bi two (double) bird prison bis two (twice) bit chewed bit piece biz business bk book bl British company bl lawman bl lawyer blue Conservative bm British Museum bm doctor bo American man boa snake board directors bob old shilling bp bishop br Britain br British br British Rail br bank rate br branch br bridge br brig br brother br brown * br lines/landline br railway(s) br trains br transport bra female support(er) bra support bra undergarment brass money brat child bren gun brer rabbit bridal old wedding bro brother bs bees bst summer time bull American policeman bull gold bus transport c Celsius/centigrade c Charles c Conservative c Cuba c about (approx.) c approx(imately) c around c cape c caput c carbon c caught c cedi c cent/centime c centi- c century c chapter c circa c club c cold c complex number c copyright c coulomb c electrical capacity c hundred c hundred thousand c key + c lot c many c note + c roughly c sea c see c speed of light c spring c tap c vitamin ca about (approx.) ca accountant ca approx(imately) ca calcium ca roughly cab transport cade conspirator cain first murderer cain killer cain murderer cal California cam river can able to + can is able to can prison can vessel cantuar archbishop cap chapter cap international car carat car transport carnation motor race cart transport cat jazz fan cato censor cattle neat cave warning cb Seabee (Amer.) cc county council cc seas cc small measure cc small quantity cc two hundred cd diplomat cd seedy ce Church of England ce church ce engineers ce this (Fr.) cent money cet this (Fr.) ch China ch Companion of Honour ch Switzerland ch award ch central heating ch champion ch chapter ch chief ch child ch church ch companion ch honour ch order cha tea chai gypsy woman chair president chal gypsy char daily che guerrilla che revolutionary cher dear (Fr.) chere dear (Fr.) chi Greek letter ci Channel Islands ci hundred and one cia secret service cia spies cid captain cid chief cid detectives cid police cid spanish hero cinc commander cl chlorine cl class cl clause cl gas - chlorine cl hundred and fifty co Colombia co business co care of co cobalt co commander co commanding officer co company co county co firm co gas - carbon monoxide co house co objector co officer cod fish cod swimmer col neck col pass cole old king colon stop com commander comb hairdresser composer scorer con Conservative con against con party con politician con study con swindle con trick cooler prison core decentralise corn naval commander cot bed cot house cow lower cow neat cr credit cr crown cr king cs Civil Service cs Czechoslovakia cs hundreds cs seas ct Connecticut ct carat ct caught ct cent/centime ct court ct small weight ct weight cu copper cu see you cue queue cure priest (Fr.) cutie pretty girl cv autobiography cy see why d (old) penny d Dee d Democrat d Deutsch d Germany d Schubert's works d copper d damn d date d daughter d day d dead/died d deci d degree d delete d delta d deserted d deuterium d diameter d diamond d differential operator d electrical flux d five hundred d four d four thousand d hundreds d key + d lot d many + d mark d note + d notice d number d strings (violin) d violin string d vitamin da American lawyer da District Attorney da agreement - foreign (Russ.) da dagger * da lawman da lawyer da yes (Russ.) dab expert dad father dad old man dail Irish house dam barrier dam mother dam restrain dame lady dan tribe das articles - German das the (Ger.) dc Washington dc Washington dc current dd cleric dd days dd divine dd doctor dd doctor of divinity dd theologian de from (Fr.) de of (Fr.) dean good man dec Christmas period dec last month decanter Tantalus' prisoner dee river deed indeed deed legal document deep in the main deep main deep sea deg degree del of the (Ital.) dela from the (Fr.) dela of the (Fr.) demi half den retreat den study der articles - German der the (Ger.) derby horse race des of the (Fr.) det detective di double di five hundred and one di princess di two (double) die articles - German die the (Ger.) dime 12.5 cents dior designer dis Hell dis Pluto dis underworld disc circle disc record disc ring dish pretty girl dit named dit reported dit said (Fr.) dit say (Fr.) diy amateur's department dk Denmark dm mark do (the) same do act do cheat do cook do ditto do note do party do work dodo double act doh note don fellow don nobleman don put on don university teacher down county dr dead reckoning dr doctor dr dram dr drawer dr healer drake bowler dt alcoholic state dt psychotic state du from the (Fr.) du of the (Fr.) dutch wife e Asian e Edward e Elizabeth e England/English e Spain e boat e bridge players e direction e east/eastern e eight e eight thousand e energy + e epsilon e eta e five e five thousand e key + e layer e logarithm base e low grade e note + e orient e oriental e point e quarter e strings (violin) e two hundred and fifty e two hundred and fifty thousand e universal set e violin string e vitamin ea East Africa ea each ea river * ea running water ea water ear listener ear organ ear spike * earp lawman eat Tanzania ebor archbishop ec London district ec city eccles Cakesville ed Edward ed editor ed journalist eden garden eden old Prime Minister eden paradise edison inventor edit censor ee ease eel fish eel swimmer eer always eer ever eer invariably eg for example eg for instance egg bomb egg cocktail egg encourage eight rowing boat ein number one (Ger.) el American railway el American railway el articles - Spanish el measure el printer's measure el small measure el the (Span.) eld old age eli priest eli prophet elia writer ell four feet ell length ell measure ely city ely city ely see em measure em printer's measure em small measure em small square em them en measure en printer's measure en small measure eng England/English ent otorhinolaryngology entry record eon age eon time ep record er Cockney girl er QE er difficulty er ever er hesitation er king er monarch er queen er royal badge era generation erasmus old scholar ere always ere before ergo so eric gradually erie lake err blunder err sin err wander erse Gaelic es French art es ease esp sixth sense